<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="O7lY5" id="O7lY5"><span data-lake-id="ua6364406" id="ua6364406">典型回答</span></h1>
  <p data-lake-id="u0df56a7d" id="u0df56a7d"><span data-lake-id="u079defcb" id="u079defcb">这里的堆是指数据结构中的堆，和操作系统内存的堆没有半毛钱关系！</span></p>
  <p data-lake-id="u33795060" id="u33795060"><span data-lake-id="u9de953cb" id="u9de953cb">​</span><br></p>
  <p data-lake-id="u8135d396" id="u8135d396"><span data-lake-id="ub5234170" id="ub5234170">堆一般是一个完全二叉树，所谓的完全二叉树就是指除了叶子节点外，其他节点都是满二叉树，也就是其他节点都是既有左节点，又有右节点的，完全二叉树如下所示：</span></p>
  <p data-lake-id="u9bd69357" id="u9bd69357"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676816641927-a86cd3f1-cf77-4987-a8d9-2c4df50531c7.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u9298edd7" id="u9298edd7"><span data-lake-id="u82161c7d" id="u82161c7d">堆是一种特殊的完全二叉树，一般分为大顶堆（大根堆）和小顶堆（小根堆）。所谓的大根堆，就是指任意节点都大于它所有的子节点，而小根堆则恰恰相反，指的是任意节点都小于它所有的子节点。如下图是一个大根堆所示：</span></p>
  <p data-lake-id="ude4f8909" id="ude4f8909"><span data-lake-id="u53de8414" id="u53de8414">​</span><br></p>
  <p data-lake-id="u099be5b4" id="u099be5b4"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676816916109-d81fa23e-e663-42d4-a44b-9f57a4c4c9cf.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_21%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u619b3455" id="u619b3455"><span data-lake-id="ue0a1222f" id="ue0a1222f">​</span><br></p>
  <p data-lake-id="u6719c619" id="u6719c619"><span data-lake-id="u3c0f2b5c" id="u3c0f2b5c">这样的性质有什么作用呢？当我们维护好一个堆之后，我们可以很容易的找到一个集合的最大值或者前K大的值，进一步思考，我们可以通过堆来实现优先队列，毕竟堆中每个元素都是权重的。Java中的优先队列PriorityQueue就是通过堆实现的。</span></p>
  <p data-lake-id="u83e43b69" id="u83e43b69"><span data-lake-id="u9982326a" id="u9982326a">​</span><br></p>
  <p data-lake-id="ucdda7208" id="ucdda7208"><span data-lake-id="ue6d567c4" id="ue6d567c4">同时，因为堆是可以动态构建的，在一些有动态数据且需要排序的场景下，堆的速度要比快排的速度快很多。譬如，TP99问题就可以通过堆来快速解决。</span></p>
  <h2 data-lake-id="VvbeS" id="VvbeS"><span data-lake-id="uc545ebf5" id="uc545ebf5">实现</span></h2>
  <p data-lake-id="u325d0df2" id="u325d0df2"><span data-lake-id="uc5ddb76c" id="uc5ddb76c">堆可以用数组或者链表实现，对于数组来说，因为堆一定是一个完全二叉树，所以堆中的每个元素一定会满足以下规律：</span></p>
  <ul list="u4f9f06eb">
   <li fid="u561f7535" data-lake-id="u61763f69" id="u61763f69"><span data-lake-id="ue325af93" id="ue325af93" style="color: rgb(18, 18, 18)">设当前节点的 cur[index] = x,</span></li>
   <li fid="u561f7535" data-lake-id="u9cfca06d" id="u9cfca06d"><span data-lake-id="ucc68a1a1" id="ucc68a1a1" style="color: rgb(18, 18, 18)">那么 parent[index] = (x-1)/2,</span></li>
   <li fid="u561f7535" data-lake-id="uca2e1984" id="uca2e1984"><span data-lake-id="u38c329b9" id="u38c329b9" style="color: rgb(18, 18, 18)">左孩子 left[index] = 2*x + 1,</span></li>
   <li fid="u561f7535" data-lake-id="u1eba64cd" id="u1eba64cd"><span data-lake-id="udc549c5b" id="udc549c5b" style="color: rgb(18, 18, 18)">右孩子 right[index] = 2*x + 2</span></li>
  </ul>
  <p data-lake-id="u3aa4a15d" id="u3aa4a15d"><span data-lake-id="u0bcc6201" id="u0bcc6201" style="color: rgb(18, 18, 18)">具体的堆化思路和实现可可以参考：</span><a href="https://www.jianshu.com/p/add3aa138f12" target="_blank" data-lake-id="u0285cd57" id="u0285cd57"><span data-lake-id="uefc2b7fb" id="uefc2b7fb">https://www.jianshu.com/p/add3aa138f12</span></a></p>
  <h1 data-lake-id="nFwMH" id="nFwMH"><span data-lake-id="uabcc3447" id="uabcc3447">知识扩展</span></h1>
  <h2 data-lake-id="nE5dv" id="nE5dv"><span data-lake-id="u1f22e16a" id="u1f22e16a">堆排序</span></h2>
  <h2 data-lake-id="cvwbz" id="cvwbz"><span data-lake-id="u74da84c0" id="u74da84c0">TOP-K问题</span></h2>
  <h2 data-lake-id="Tu449" id="Tu449"><span data-lake-id="u9f82b0f5" id="u9f82b0f5">什么是TP99问题，如何快速计算？</span></h2>
  <p data-lake-id="u6f53f850" id="u6f53f850"><span data-lake-id="ua0afe96b" id="ua0afe96b">所谓的TP99，指的是在一个时间段内，统计某个接口（或方法）每次调用所消耗的时间，并将这些时间按从小到大的顺序进行排序，取第99%的那个值作为TP99值。</span></p>
  <p data-lake-id="ud53ba366" id="ud53ba366"><span data-lake-id="uf755cb00" id="uf755cb00">​</span><br></p>
  <p data-lake-id="u01750bf7" id="u01750bf7"><span data-lake-id="u838517ef" id="u838517ef">举个例子， 假设某个方法在5分钟内调用消耗时间的TP99为10ms，那么就说明该接口5分钟内前99%的调用时间都是10ms，看起来接口性能还不错。所以TP99一般是统计性能的一个指标。</span></p>
  <p data-lake-id="u1e4df13e" id="u1e4df13e"><span data-lake-id="ufb39b430" id="ufb39b430">​</span><br></p>
  <p data-lake-id="u42cd56b5" id="u42cd56b5"><span data-lake-id="uee1231f6" id="uee1231f6">计算TP99也需要用到堆，思路如下：</span></p>
  <p data-lake-id="u8b92a51a" id="u8b92a51a"><span data-lake-id="u482d029c" id="u482d029c">​</span><br></p>
  <p data-lake-id="uca2324ce" id="uca2324ce"><span data-lake-id="uf15ccffe" id="uf15ccffe">创建一个大顶堆和一个小顶堆，大顶堆的堆顶元素比小顶堆的堆顶元素更小，大顶堆维护 99% 的请求时间，小顶堆维护 1% 的请求时间</span></p>
  <p data-lake-id="ue678ff96" id="ue678ff96"><span data-lake-id="u4bf0d960" id="u4bf0d960">​</span><br></p>
  <p data-lake-id="ud458fc98" id="ud458fc98"><span data-lake-id="uade31509" id="uade31509">每产生一个元素（请求时间），如果它比大顶堆的堆顶元素小，则将其放入到大顶堆中，如果它比小顶堆的堆顶元素大，则将其插入到小顶堆中，插入后当然要堆化以让其符合大小顶堆的要求。</span></p>
  <p data-lake-id="u1f2620ef" id="u1f2620ef"><span data-lake-id="u02cad73e" id="u02cad73e">​</span><br></p>
  <p data-lake-id="uc3d8bff7" id="uc3d8bff7"><span data-lake-id="u871c7ccd" id="u871c7ccd">上一步在插入的过程中需要注意一下，可能会导致大顶堆和小顶堆中元素的比例不为 99:1，此时就要做相应的调整，如果在将元素插入大顶堆之后，发现比例大于 99：1，将需将大顶堆的堆顶元素移到小顶堆中，再对两个堆堆化以让其符合大小顶堆的要求，同理，如果发现比例小于99: 1，则需要将小顶堆的堆顶元素移到大顶堆来，再对两者进行堆化。</span></p>
  <p data-lake-id="u964e5c30" id="u964e5c30"><span data-lake-id="ua846cf5c" id="ua846cf5c">​</span><br></p>
  <p data-lake-id="uaffdac21" id="uaffdac21"><span data-lake-id="uc10e43bd" id="uc10e43bd">以上的大小顶堆调整后，则大顶堆的堆顶元素值就是所要求的 TP99值。</span></p>
  <p data-lake-id="u8a977cdb" id="u8a977cdb"><span data-lake-id="ua510ac84" id="ua510ac84">​</span><br></p>
  <p data-lake-id="u01d26c7b" id="u01d26c7b"><span data-lake-id="u1421fdfc" id="u1421fdfc">用排序也可以解决该问题，但是堆是可以实时获取TP99的，使用排序只能在时间结束后堆所有数据进行排序才可以。</span></p>
 </body>
</html>